from Tree import TreeNode, bfs_load

class Solution:
    # FIXME 中序遍历
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def isLegal(parent, high, low):
            if parent is None:
                return 1
            if parent.left:
                if parent.left.val < low.val:
                    parent.left.val, low.val = low.val, parent.left.val
                    return 1
                elif parent.left.val > parent.val:
                    parent.left.val, parent.val = parent.val, parent.left.val
                    return 1
            if parent.right:
                if parent.right.val < parent.val:
                    parent.right.val, parent.val = parent.val, parent.right.val
                    return 1
                elif parent.right.val > high.val:
                    parent.right.val, high.val = high.val, parent.right.val
                    return 1
            if isLegal(parent.left, parent, low) and isLegal(parent.right, high, parent):
                return 1
        h, l = TreeNode(val=2**31), TreeNode(val=-2**31-1)
        isLegal(root, h, l)

if __name__ == '__main__':
    c = Solution()
    mylist = [2,3]
    root = bfs_load(mylist)
    print(root.bfs_show())
    c.recoverTree(root)
    print(root.bfs_show())